//
// Created by bleedingfight on 2020/7/4.
//

#include "maxValue.h"
int maxValue(std::vector<std::vector<int>>& grid){
    const int rows = grid.size();
    if(rows == 0)
        return 0;
    const int cols = grid[0].size();
    if(cols == 0)
        return 0;
    std::vector<int>sum_dp = std::vector<int>(cols,0);
    for(int row =0;row<rows;row++){
        for(int col=0;col<cols;col++){
            if(col == 0 && row == 0)
                sum_dp[col] = grid[row][col];
            else if(row == 0 && col!=0)
                sum_dp[col] = grid[row][col]+sum_dp[col-1];
            else if(row !=0 && col==0)
                sum_dp[col] = grid[row][col]+sum_dp[col];
            else
            {
                int left = sum_dp[col-1];
                int upper = sum_dp[col];
                if(left>upper){
                    sum_dp[col]=left+grid[row][col];
                } else{
                    sum_dp[col]=upper+grid[row][col];
                }
            }
        }
    }
    return sum_dp[cols-1];
}
